A “multi-hop network” generally refers to a network where items are transported to destinations over multiple nodes or “hops.” For example, in wired and wireless communication networks, voice or data traffic is routinely routed over multiple hops to its destination. Specific examples include communication networks used in buildings, large industrial facilities, and Advanced Metering Infrastructure (AMI) systems. As another example, mobile networks can include wireless devices that constantly change positions and communicate over ever-changing communication links. Specific examples include swarms of unmanned aerial vehicles, groups of soldiers with mobile devices, or fleets of transport vehicles. As yet is another example, a power distribution grid can route power to different customers over multiple transmission lines. As still other examples, transportation networks (such as road, rail, or air systems) can transport people or materials over different routes, and social networks may involve numerous people having different relationships.
A specific example of a multi-hop wireless network is a mesh network. In this type of network, data can be passed from a source node to a destination node directly or via one or more intermediate nodes. Consider a multi-hop sensor network where wireless sensors publish sensor readings to a gateway. Not all sensors may be in direct communication range to the gateway, so some sensors can send information to the gateway through other sensors that are closer to the gateway.
Multi-hop networks are often robust and resilient to node or link failures because the networks are often able to re-route or re-connect a path from a source node to a destination node when an intermediate node or link fails. For this reason, these types of networks are often called “self-healing” networks. Although the ability to self-heal is well developed, self-healing may not always be possible. The topology of a multi-hop network plays an important role in being able to send information from any given source node to any given destination node in the face of link and node failures.
The self-healing nature of multi-hop networks often gives designers and implementers a false hope that a network is robust to node and link failures, while the topology of the network may actually make it impossible for self-healing to occur. The inability of a multi-hop network to self-heal can cause various problems, ranging from inconvenient to life-threatening. For instance, the failure of a power distribution node could cause an inconvenient power loss to homeowners or businesses. The failure of a wireless node in a military network could prevent communications with a group of soldiers on a battlefield.
In conventional systems, a brute-force approach is often taken to identify when a network may be unable to self-heal. In this approach, the removal of a node from a network is simulated, and a determination is made whether routes exist from each potential source node to each potential destination node. If not, the loss of the removed node can divide the network and prevent self-healing. However, this approach is very time consuming and computationally intensive. Also, this approach is particularly problematic if the topology of a network is constantly changing.